import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/23 10:19
 * @description
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        List<List<Integer>> forest = new ArrayList<>();
        List<Integer> integers = new ArrayList<>();
        integers.add(1);
        integers.add(2);
        integers.add(4);
        List<Integer> integers1 = new ArrayList<>();
        integers1.add(3);
        integers1.add(0);
        integers1.add(6);
        List<Integer> integers2 = new ArrayList<>();
        integers2.add(7);
        integers2.add(8);
        integers2.add(9);
        forest.add(integers);
        forest.add(integers1);
        forest.add(integers2);
        solution.cutOffTree(forest);
    }
    int m, n;
    int[][] dirs = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
    int[][] tree;
    public int cutOffTree(List<List<Integer>> forest) {
        List<int[]> treeLoc = new ArrayList<>();
        m = forest.size();
        n = forest.get(0).size();
        tree = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                tree[i][j] = forest.get(i).get(j);
                if (tree[i][j] > 1) {
                    treeLoc.add(new int[]{i, j});
                }
            }
        }
        // 按树高度升序排序，那么treeLoc为砍树顺序
        Collections.sort(treeLoc, (a , b) -> tree[a[0]][a[1]] - tree[b[0]][b[1]]);

        int cx = 0, cy = 0;
        int ans = 0;
        for (int i = 0; i < treeLoc.size(); i++) {
            int nx = treeLoc.get(i)[0], ny = treeLoc.get(i)[1];
            int steps = bfs(cx, cy, nx, ny);
            if (steps == -1) {
                // 不能到达下一个
                return -1;
            }
            ans += steps;
            cx = nx;
            cy = ny;
        }
        return ans;
    }

    /**
     * 高度相邻的两棵树之间的最短距离
     * @param sx 当前树横坐标sx
     * @param sy ...sy
     * @param tx 下一棵树 tx
     * @param ty ... ty
     * @return 最短距离
     */
    public int bfs(int sx, int sy, int tx, int ty) {
        if (sx == tx && sy == ty) {
            return 0;
        }
        int step = 0;
        Queue<int[]> queue = new ArrayDeque<>();
        boolean[][] vis = new boolean[m][n];
        queue.offer(new int[] {sx, sy});
        vis[sx][sy] = true;
        while (!queue.isEmpty()) {
            step++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] cell = queue.poll();
                int cx = cell[0], cy = cell[1];
                for (int j = 0; j < 4; j++) {
                    int nx = cx + dirs[j][0], ny = cy + dirs[j][1];
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                        if (nx == tx && ny == ty) {
                            tree[nx][ny] = 1;
                            return step;
                        }
                        if (!vis[nx][ny] && tree[nx][ny] > 0 && tree[nx][ny] < tree[tx][ty]) {
                            queue.offer(new int[] {nx, ny});
                            vis[nx][ny] = true;
                        }
                    }
                }
            }
        }
        return -1;
    }
}
